﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ComputationalGeometry.DataStructures
{
    public class BinaryHeap<T> : ICloneable where T : IComparable<T>
    {
        private List<T> _heap;
        private IComparer<T> _comparer = Comparer<T>.Default;
        private MinMax _minmax;

        public object Clone()
        {
            BinaryHeap<T> heap = new BinaryHeap<T>(this._minmax);
            heap._heap = new List<T>(_heap);

            return heap;
        }

        public BinaryHeap(MinMax minmax = MinMax.Max)
        {
            _heap = new List<T>();
            _minmax = minmax;
        }

        public int Count
        {
            get { return this._heap.Count; }
        }

        public void Push(T item)
        {
            _heap.Add(item);
            UpMaxHeap(_heap.Count - 1);
        }

        public T Pop()
        {
            T top = _heap[0];
            int last = _heap.Count - 1;
            _heap[0] = _heap[last];
            _heap.RemoveAt(last);
            DownMaxHeap(0);

            return top;
        }

        public T Top()
        {
            return _heap[0];
        }

        public IEnumerable<T> GetSortedList()
        {
            BinaryHeap<T> heapCopy = (BinaryHeap<T>)this.Clone();
            List<T> sortedList = new List<T>();

            while (heapCopy.Count != 0)
            {
                sortedList.Add(heapCopy.Pop());
            }

            return sortedList;
        }

        private bool IsGreaterThan(int left, int right)
        {
            return _comparer.Compare(_heap[left], _heap[right]) > 0;
        }

        private void SwapItems(int item1, int item2)
        {
            T temp = _heap[item1];
            _heap[item1] = _heap[item2];
            _heap[item2] = temp;
        }

        private void UpMaxHeap(int start)
        {
            int current = start;
            while(current > 0)
            {
                int parent = this.Parent(current);
                if(IsGreaterThan(current, parent))
                {
                    SwapItems(current, parent);
                    current = parent;
                }
                else
                    break;
            }
        }

        private void DownMaxHeap(int start)
        {
            int current = start;
            int leftChild = 0;
            int rightChild = 0;
            int largest = 0;
            int lastItem = _heap.Count - 1;

            while(true)
            {
                leftChild = 2 * current + 1;
                rightChild = 2 * current + 2;

                if(leftChild <= (lastItem) && IsGreaterThan(leftChild, current))
                {
                    largest = leftChild;
                }
                else
                {
                    largest = current;
                }

                if(rightChild <= (lastItem) && IsGreaterThan(rightChild, largest))
                {
                    largest = rightChild;
                }

                if(largest != current)
                {
                    SwapItems(current, largest);
                    current = largest;
                }
                else
                    break;
            }        
        }

        private int Parent(int index)
        {
            if (index < 0)
                throw new ArgumentOutOfRangeException("Index is less than zero.");
            else if (index == 0)
                return 0;
            else
            {
                // floats will get truncated for integer types: 5 / 2 = 2
                return (index - 1) / 2;
            }
        }
    }
}
